package org.example.leetCode;

import org.example.entity.ListNode;

import java.util.HashMap;

/**
 * 160. 相交链表
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
 * 如果两个链表不存在相交节点，返回 null 。
 */
public class Code160 {
    /**
     * 方法一：哈希表解法（原始方法）
     * 时间复杂度：O(m+n)
     * 空间复杂度：O(m)
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashMap<ListNode, Integer> map = new HashMap<>();
        ListNode cur = headA, curB = headB;
        while (cur != null) {
            map.put(cur, cur.val);
            cur = cur.next;
        }
        while (curB != null) {
            if (map.containsKey(curB)) {
                return curB;
            }
            curB = curB.next;
        }
        return null;
    }

    /**
     * 方法二：双指针解法（优化方法）
     * 时间复杂度：O(m+n)
     * 空间复杂度：O(1)
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pointerA = headA;
        ListNode pointerB = headB;

        // 当两个指针不相等时继续遍历
        while (pointerA != pointerB) {
            // pointerA遍历完链表A后，从链表B开始遍历
            pointerA = pointerA == null ? headB : pointerA.next;
            // pointerB遍历完链表B后，从链表A开始遍历
            pointerB = pointerB == null ? headA : pointerB.next;
        }

        // 如果相交，返回相交节点；如果不相交，都为null
        return pointerA;
    }
}
